//! Unsafe list head 实现
//!
//! Unsafe list head 的实现是 linux 的 `list_head` 实现.
//! 这个模块是一个非常底层的接口, 没有并发支持, 没有所有权,
//! 操作的对象都是裸指针, 所有操作均是 unsafe 的.
//! 这个模块的实现只是为了方便实现 page alloc 接口.
#![no_std]
#![allow(unsafe_code)]

/// 链表标识1
pub const LIST_POISON1: usize = 0xdead0100;
/// 链表标识2
pub const LIST_POISON2: usize = 0xdead0200;

/// 链表头
#[derive(Clone, Copy)]
pub struct UnsafeListHead<T> {
    next: *mut UnsafeListNode<T>,
    prev: *mut UnsafeListNode<T>,
    offset: usize,
}

impl<T> Default for UnsafeListHead<T> {
    fn default() -> Self {
        Self::new()
    }
}

impl<T> UnsafeListHead<T> {
    /// 构造一个链表(未初始化)
    ///
    /// 需要调用`init_list_head`初始化才能使用
    pub const fn new() -> Self {
        let init = core::ptr::null_mut::<UnsafeListNode<T>>();
        Self { next: init, prev: init, offset: 0 }
    }

    /// 初始化链表头
    pub fn init_list_head(&mut self, offset: usize) {
        let ptr = (self as *mut UnsafeListHead<T>).cast::<UnsafeListNode<T>>();
        unsafe {
            core::ptr::write_volatile(&mut self.next, ptr);
        }
        self.prev = ptr;
        self.offset = offset;
    }

    #[inline(always)]
    unsafe fn __list_add(
        new: &mut UnsafeListNode<T>,
        prev: &mut UnsafeListNode<T>,
        next: &mut UnsafeListNode<T>,
    ) {
        next.prev = new;
        new.next = next;
        new.prev = prev;
        core::ptr::write_volatile(&mut prev.next, new);
    }

    /// # Safety
    ///
    /// 确保数据不会被 rust 所有权机制释放, 如果存在并发, 请保证一切操作的原子性.
    #[inline(always)]
    pub unsafe fn list_add(&mut self, new: &mut UnsafeListNode<T>) {
        UnsafeListHead::__list_add(
            new,
            &mut *(self as *mut UnsafeListHead<T>).cast::<UnsafeListNode<T>>(),
            &mut *self.next,
        );
    }

    /// # Safety
    ///
    /// 确保数据不会被 rust 所有权机制释放, 如果存在并发, 请保证一切操作的原子性.
    #[inline(always)]
    pub unsafe fn list_add_tail(&mut self, new: &mut UnsafeListNode<T>) {
        UnsafeListHead::__list_add(
            new,
            &mut *self.prev,
            &mut *(self as *mut UnsafeListHead<T>).cast::<UnsafeListNode<T>>(),
        );
    }

    /// # Safety
    ///
    /// 确保数据不会被 rust 所有权机制释放, 如果存在并发, 请保证一切操作的原子性.
    #[inline(always)]
    pub unsafe fn list_is_last(&self, list: &mut UnsafeListNode<T>) -> bool {
        core::ptr::eq(
            list.next as *const UnsafeListNode<T>,
            (self as *const UnsafeListHead<T>).cast::<UnsafeListNode<T>>(),
        )
    }

    /// # Safety
    ///
    /// 确保数据不会被 rust 所有权机制释放, 如果存在并发, 请保证一切操作的原子性.
    #[inline(always)]
    pub unsafe fn list_empty(&self) -> bool {
        core::ptr::eq(
            core::ptr::read_volatile(&self.next) as *const UnsafeListNode<T>,
            (self as *const UnsafeListHead<T>).cast::<UnsafeListNode<T>>(),
        )
    }

    /// # Safety
    ///
    /// 确保数据不会被 rust 所有权机制释放, 如果存在并发, 请保证一切操作的原子性.
    #[inline(always)]
    pub unsafe fn list_empty_careful(&self) -> bool {
        let next = self.next as *const UnsafeListNode<T>;
        next == (self as *const UnsafeListHead<T>).cast::<UnsafeListNode<T>>() && next == self.prev
    }

    /// # Safety
    ///
    /// 确保数据不会被 rust 所有权机制释放, 如果存在并发, 请保证一切操作的原子性.
    #[inline(always)]
    pub unsafe fn list_first_entry_or_null(&self) -> Option<&T> {
        let next = self.next;
        if core::ptr::eq(
            next as *const UnsafeListNode<T>,
            (self as *const UnsafeListHead<T>).cast::<UnsafeListNode<T>>(),
        ) {
            None
        } else {
            Some(&*((next as usize - self.offset) as *const T))
        }
    }

    /// # Safety
    ///
    /// 确保数据不会被 rust 所有权机制释放, 如果存在并发, 请保证一切操作的原子性.
    #[inline(always)]
    pub unsafe fn list_first_entry_or_null_mut(&mut self) -> Option<&mut T> {
        let next = self.next;
        if next == (self as *mut UnsafeListHead<T>).cast::<UnsafeListNode<T>>() {
            None
        } else {
            Some(&mut *((next as usize - self.offset) as *mut T))
        }
    }

    /// # Safety
    ///
    /// 确保数据不会被 rust 所有权机制释放, 如果存在并发, 请保证一切操作的原子性.
    #[inline(always)]
    pub unsafe fn list_first_entry_mut(&mut self) -> &mut T {
        &mut *((self.next as usize - self.offset) as *mut T)
    }

    /// # Safety
    ///
    /// 确保数据不会被 rust 所有权机制释放, 如果存在并发, 请保证一切操作的原子性.
    #[inline(always)]
    pub unsafe fn list_first_entry(&self) -> &T {
        &*((self.next as usize - self.offset) as *const T)
    }

    /// # Safety
    ///
    /// 确保数据不会被 rust 所有权机制释放, 如果存在并发, 请保证一切操作的原子性.
    #[inline(always)]
    pub unsafe fn list_last_entry_mut(&mut self) -> &mut T {
        &mut *((self.prev as usize - self.offset) as *mut T)
    }

    /// # Safety
    ///
    /// 确保数据不会被 rust 所有权机制释放, 如果存在并发, 请保证一切操作的原子性.
    #[inline(always)]
    pub unsafe fn list_last_entry(&self) -> &T {
        &*((self.prev as usize - self.offset) as *const T)
    }
}

/// 初始化链表头
#[macro_export]
macro_rules! init_unsafe_list_head {
    ($var:ident, $type:ty, $($member:tt).+ $(,)?) => {
        $var.init_list_head(core::mem::offset_of!($type, $($member).+));
    };
}

/// 定义并初始化链表头
#[macro_export]
macro_rules! define_unsafe_list_head {
    ($var:ident, $type:ty, $($member:tt).+ $(,)?) => {
        let mut $var = $crate::UnsafeListHead::<$type>::new();
        $crate::init_unsafe_list_head!($var, $type, $($member).+);
    };
}

/// 链表节点
#[derive(Clone, Copy)]
pub struct UnsafeListNode<T> {
    next: *mut UnsafeListNode<T>,
    prev: *mut UnsafeListNode<T>,
}

impl<T> Default for UnsafeListNode<T> {
    fn default() -> Self {
        Self::new()
    }
}

impl<T> UnsafeListNode<T> {
    /// 构造一个链表节点
    pub const fn new() -> Self {
        let init = core::ptr::null_mut::<UnsafeListNode<T>>();
        Self { next: init, prev: init }
    }

    #[inline(always)]
    unsafe fn init_list_node(&mut self) {
        let value = self as *mut UnsafeListNode<T>;
        core::ptr::write_volatile(&mut self.next, value);
        self.prev = value;
    }

    #[inline(always)]
    unsafe fn __list_del(prev: &mut UnsafeListNode<T>, next: &mut UnsafeListNode<T>) {
        next.prev = prev;
        core::ptr::write_volatile(&mut prev.next, next);
    }

    #[inline(always)]
    unsafe fn __list_del_entry(&mut self) {
        UnsafeListNode::__list_del(&mut *self.prev, &mut *self.next);
    }

    /// # Safety
    ///
    /// 确保数据不会被 rust 所有权机制释放, 如果存在并发, 请保证一切操作的原子性.
    #[inline(always)]
    pub unsafe fn list_del(&mut self) {
        self.__list_del_entry();
        self.next = LIST_POISON1 as *mut UnsafeListNode<T>;
        self.prev = LIST_POISON2 as *mut UnsafeListNode<T>;
    }

    /// # Safety
    ///
    /// 确保数据不会被 rust 所有权机制释放, 如果存在并发, 请保证一切操作的原子性.
    #[inline(always)]
    pub unsafe fn list_replace(&mut self, new: &mut UnsafeListNode<T>) {
        new.next = self.next;
        (*new.next).prev = new;
        new.prev = self.prev;
        (*new.prev).next = new;
    }

    /// # Safety
    ///
    /// 确保数据不会被 rust 所有权机制释放, 如果存在并发, 请保证一切操作的原子性.
    #[inline(always)]
    pub unsafe fn list_replace_init(&mut self, new: &mut UnsafeListNode<T>) {
        self.list_replace(new);
        self.init_list_node();
    }

    /// # Safety
    ///
    /// 确保数据不会被 rust 所有权机制释放, 如果存在并发, 请保证一切操作的原子性.
    #[inline(always)]
    pub unsafe fn list_del_init(&mut self) {
        self.__list_del_entry();
        self.init_list_node();
    }

    /// # Safety
    ///
    /// 确保数据不会被 rust 所有权机制释放, 如果存在并发, 请保证一切操作的原子性.
    #[inline(always)]
    pub unsafe fn list_move(&mut self, head: &mut UnsafeListHead<T>) {
        self.__list_del_entry();
        head.list_add(self);
    }

    /// # Safety
    ///
    /// 确保数据不会被 rust 所有权机制释放, 如果存在并发, 请保证一切操作的原子性.
    #[inline(always)]
    pub unsafe fn list_move_tail(&mut self, head: &mut UnsafeListHead<T>) {
        self.__list_del_entry();
        head.list_add_tail(self);
    }

    #[inline(always)]
    unsafe fn list_next_entry_mut(&mut self, offset: usize) -> &mut T {
        &mut *((self.next as usize - offset) as *mut T)
    }

    #[inline(always)]
    unsafe fn list_next_entry(&self, offset: usize) -> &T {
        &*((self.next as usize - offset) as *const T)
    }

    #[inline(always)]
    unsafe fn list_prev_entry_mut(&mut self, offset: usize) -> &mut T {
        &mut *((self.prev as usize - offset) as *mut T)
    }

    #[inline(always)]
    unsafe fn list_prev_entry(&self, offset: usize) -> &T {
        &*((self.prev as usize - offset) as *const T)
    }
}

/// 链表迭代器
pub struct UnsafeListHeadIter<'a, T> {
    prev_pos: *const UnsafeListNode<T>,
    next_pos: *const UnsafeListNode<T>,
    head: &'a UnsafeListHead<T>,
}

impl<'a, T> UnsafeListHeadIter<'a, T> {
    fn new(head: &'a UnsafeListHead<T>) -> Self {
        let init = core::ptr::null::<UnsafeListNode<T>>();
        Self { prev_pos: init, next_pos: init, head }
    }
}

impl<T> UnsafeListHead<T> {
    /// 创建迭代器
    pub fn iter(&self) -> UnsafeListHeadIter<T> {
        UnsafeListHeadIter::new(self)
    }
}

impl<'a, T> Iterator for UnsafeListHeadIter<'a, T> {
    type Item = &'a T;
    fn next(&mut self) -> Option<Self::Item> {
        unsafe {
            if self.next_pos.is_null() {
                self.next_pos = self.head.next;
                return Some(self.head.list_first_entry());
            }

            let this = (*self.next_pos).next as *const UnsafeListNode<T>;
            let end = if self.prev_pos.is_null() {
                (self.head as *const UnsafeListHead<T>).cast::<UnsafeListNode<T>>()
            } else {
                self.prev_pos
            };
            if this == end {
                return None;
            }

            let val = (*self.next_pos).list_next_entry(self.head.offset);
            self.next_pos = (*self.next_pos).next;
            Some(val)
        }
    }
}

impl<'a, T> DoubleEndedIterator for UnsafeListHeadIter<'a, T> {
    fn next_back(&mut self) -> Option<&'a T> {
        unsafe {
            if self.prev_pos.is_null() {
                self.prev_pos = self.head.prev;
                return Some(self.head.list_last_entry());
            }

            let this = (*self.prev_pos).prev as *const UnsafeListNode<T>;
            let end = if self.next_pos.is_null() {
                (self.head as *const UnsafeListHead<T>).cast::<UnsafeListNode<T>>()
            } else {
                self.next_pos
            };
            if this == end {
                return None;
            }

            let val = (*self.prev_pos).list_prev_entry(self.head.offset);
            self.prev_pos = (*self.prev_pos).prev;
            Some(val)
        }
    }
}

/// 链表可变迭代器
pub struct UnsafeListHeadIterMut<'a, T> {
    prev_pos: *mut UnsafeListNode<T>,
    next_pos: *mut UnsafeListNode<T>,
    head: &'a mut UnsafeListHead<T>,
}

impl<'a, T> UnsafeListHeadIterMut<'a, T> {
    fn new(head: &'a mut UnsafeListHead<T>) -> Self {
        let init = core::ptr::null_mut::<UnsafeListNode<T>>();
        Self { prev_pos: init, next_pos: init, head }
    }
}

impl<T> UnsafeListHead<T> {
    /// 创建可变迭代器
    pub fn iter_mut(&mut self) -> UnsafeListHeadIterMut<T> {
        UnsafeListHeadIterMut::new(self)
    }
}

impl<'a, T> Iterator for UnsafeListHeadIterMut<'a, T> {
    type Item = &'a mut T;
    fn next(&mut self) -> Option<Self::Item> {
        unsafe {
            if self.next_pos.is_null() {
                self.next_pos = self.head.next;
                let this = self.head as *mut UnsafeListHead<T>;
                return Some((*this).list_first_entry_mut());
            }

            let this = (*self.next_pos).next as *const UnsafeListNode<T>;
            let end = if self.prev_pos.is_null() {
                (self.head as *const UnsafeListHead<T>).cast::<UnsafeListNode<T>>()
            } else {
                self.prev_pos
            };
            if this == end {
                return None;
            }

            let val = (*self.next_pos).list_next_entry_mut(self.head.offset);
            self.next_pos = (*self.next_pos).next;
            Some(val)
        }
    }
}

impl<'a, T> DoubleEndedIterator for UnsafeListHeadIterMut<'a, T> {
    fn next_back(&mut self) -> Option<&'a mut T> {
        unsafe {
            if self.prev_pos.is_null() {
                self.prev_pos = self.head.prev;
                let this = self.head as *mut UnsafeListHead<T>;
                return Some((*this).list_last_entry_mut());
            }

            let this = (*self.prev_pos).prev as *const UnsafeListNode<T>;
            let end = if self.next_pos.is_null() {
                (self.head as *const UnsafeListHead<T>).cast::<UnsafeListNode<T>>()
            } else {
                self.next_pos
            };
            if this == end {
                return None;
            }

            let val = (*self.prev_pos).list_prev_entry_mut(self.head.offset);
            self.prev_pos = (*self.prev_pos).prev;
            Some(val)
        }
    }
}
